public class Demo {
    /*
    gitalgorithmDemo
     */
    public static void main(String[] args) {

//        System.out.println("Hello algorithm");

        //斐波那契数列
        int res = fabonacii(40);
        System.out.println(res);
        print(40);
    }
    /**
     * 斐波那契数列的第n项
     * @param n
     * @return
     */
    public static int fabonacii(int n) {

        //使用递归：当n比较大时由于代码中包含两次递归调用所以运行速度明显变慢
        //从1开始也就是第一项是1
//        if(n < 1) {
//            throw new RuntimeException("输入的参数不合法");
//        }
//        if(n == 1 || n == 2) {
//            return 1;
//        }else {
//            return fabonacii(n-1)+fabonacii(n-2);
//        }

        //从0开始，也就是第一项是0
//        if(n==1){
//            return 0;
//        }
//        if (n==2){
//            return 1;
//        }
//        return fabonacii(n-1)+fabonacii(n-2);
//
        //使用迭代：可以改善算法运行效率，用空间换时间
        //从一开始
        if (n<2){
            return n;
        }

        int f= 0;
        int g= 1;
        int result =0;
        for (int i =1;i<n;i++){
            result =f+g;
            f=g;
            g=result;
        }
        return result;
    }

    /**
     * 输出前n项斐波那契数列
     * @param n
     */
    public static void print(int n) {
        for (int i = 1; i <= n; i++) {
            System.out.print(fabonacii(i)+" ");
        }
    }
}
